// 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

// 示例:

// 输入: [5,2,6,1]
// 输出: [2,1,1,0] 
// 解释:
// 5 的右侧有 2 个更小的元素 (2 和 1).
// 2 的右侧仅有 1 个更小的元素 (1).
// 6 的右侧有 1 个更小的元素 (1).
// 1 的右侧有 0 个更小的元素.

#include <vector>
#include <algorithm>

using namespace std;

// 暴力搜索， 超时
// O(n^2)
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> counts(n, 0);
        for (int i{0}; i < n - 1; ++i) {
            for (int j{i + 1}; j < n; ++j) {
                if (nums[i] > nums[j]) ++counts[i];
            }
        }
        return counts;
    }
};

/*
离散化树状数组
「树状数组」是一种可以动态维护序列前缀和的数据结构，它的功能是：
    单点更新 update(i, v)： 把序列 i 位置的数加上一个值 v，在该题中 v = 1
    区间查询 query(i)： 查询序列 [1⋯i] 区间的区间和，即 i 位置的前缀和
    修改和查询的时间代价都是 O(logn)，其中 n 为需要维护前缀和的序列的长度。
时间复杂度：O(NlogN)
空间复杂度：O(N)
*/
class Solution {
private:
    vector<int> c{};
    vector<int> a{};
    void init(int len) {
        c.resize(len, 0);
    }
    int lowBit(int x) { // lowbit(x)是x的二进制表达式中最低位的1所对应的值
        return x & (-x);
    }
    void update(int pos) {
        while (pos < c.size()) {
            c[pos] += 1;
            pos += lowBit(pos);
        }
    }
    int query(int pos) {
        int ret{0};
        while (pos > 0) {
            ret += c[pos];
            pos -= lowBit(pos);
        }
        return ret;
    }
    // 离散化
    void discretization(const vector<int>& nums) {
        a.assign(nums.begin(), nums.end());
        sort(a.begin(), a.end()); // 排序
        // 去重，unique()返回去重后容器中不重复序列的最后一个元素的下一个元素的迭代器。
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    // 获取x的下标
    int getId(int x) {
        // 二分查找数值第一次出现的位置
        return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> counts{};
        discretization(nums);
        init(nums.size() + 5);
        for (int i = nums.size() - 1; i >= 0; --i) {
            int id = getId(nums[i]);
            counts.push_back(query(id - 1));
            update(id);
        }
        reverse(counts.begin(), counts.end());
        return counts;
    }
};